#include <bits/stdc++.h>
using namespace std;
// 递归解法
class Solution
{
public:
    int ret = INT_MAX;
    int integerReplacement(int n)
    {
        dfs(n, 0);
        return ret;
    }
    void dfs(long long int n, int count)
    {
        if (n <= 1)
        {
            ret = min(ret, count);
            return;
        }
        if (n % 2 == 0)
        {
            dfs(n / 2, count + 1);
        }
        else
        {
            dfs(n + 1, count + 1);
            dfs(n - 1, count + 1);
        }
    }
};

// 记忆化搜索
class Solution1
{
public:
    unordered_map<int, int> dp;
    int integerReplacement(int n)
    {
        if (n < 0)
        {
            return 0;
        }
        if (n == 0)
        {
            dp[0] = 1;
            return 1;
        }
        if (n == 1)
        {
            dp[1] = 0;
            return 0;
        }
        if (n == 2)
        {
            dp[2] = 1;
            return 1;
        }
        if (dp.count(n))
            return dp[n];
        if (n % 2 == 0)
        {
            dp[n] = 1 + integerReplacement(n / 2);
            return dp[n];
        }

        // 奇数加1减1最后都是进行/2 例如 5 加1减去1就是3 2
        dp[n] = min(integerReplacement(n / 2 + 1), integerReplacement(n / 2)) + 2;

        return dp[n];
    }
};
class Solution 
{
public:
    unordered_map<int,int>dp;
    int integerReplacement(int n1) 
    {
        long long int n=n1;
        int ret=0;
        while(n>1)
        {
            if(n%2==0)
            {
                n/=2;
                ret++;
            }
            else
            {
                if(n==3)
                {
                    n--;
                    ret++;
                }
                else if(n%4==1)
                {
                    n--;
                    ret++;
                }
                else if(n%4==3)
                {
                    n++;
                    ret++;
                }
            }
        }
        return ret;
    }
   
};